package com.kehao.leetcode.hard.backtracking;

import org.junit.Test;

import javax.jnlp.ClipboardService;
import javax.print.attribute.standard.PresentationDirection;
import javax.swing.*;
import java.util.*;

public class PartitionSolution {
    private Map<String,List> map = new HashMap<>();

    public List<List<String>> partition(String s) {
        List<List<String>> result = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            String s1 = s.charAt(i) + "";
            List<List<String>> value = new LinkedList<>();
            List<String> stringList = new LinkedList<>();
            stringList.add(s1);
            value.add(stringList);
            map.put(s1,value);
        }
        for (int i = 1; i < s.length(); i++) {
            String s1 = s.substring(0,i);
            if(isPalindromeString(s1)){
                String s2 = s.substring(i);
                List<List<String>> subStringList =partitionSubString(s2);
                for (List<String> stringList : subStringList) {
                    List<String> oneResult = new LinkedList<>();
                    oneResult.add(s1);
                    stringList.forEach(str->oneResult.add(str));
                    result.add(oneResult);
                }
            }
        }
        if(isPalindromeString(s)){
            List<String> stringList = new LinkedList<>();
            stringList.add(s);
            result.add(stringList);
            return result;
        }
        return result;
    }

    private List<List<String>> partitionSubString(String s){
        if(map.containsKey(s)) return map.get(s);
        List<List<String>> result = new LinkedList<>();
        for (int i = 1; i < s.length(); i++) {
            String s1 = s.substring(0,i);
            if(isPalindromeString(s1)){
                String s2 = s.substring(i);
                List<List<String>> subStringList =partitionSubString(s2);
                for (List<String> stringList : subStringList) {
                    List<String> oneResult = new LinkedList<>();
                    oneResult.add(s1);
                    stringList.forEach(str->oneResult.add(str));
                    result.add(oneResult);
                }
            }
        }
        if(isPalindromeString(s)){
            List<String> stringList = new LinkedList<>();
            stringList.add(s);
            result.add(stringList);
        }
        map.put(s,result);
        return result;
    }

    private boolean isPalindromeString(String s){
        for (int i = 0; i < s.length() / 2; i++) {
            if(s.charAt(i)!=s.charAt(s.length()-1-i)){
                return false;
            }
        }
        return true;
    }

    @Test
    public void test01(){
        System.out.println(partition("aab"));
    }

    @Test
    public void test02(){
        System.out.println(partition("a"));
    }

    @Test
    public void test03(){
        System.out.println(partition("cbbbcc"));
    }
}
